package com.wyr.leetcode.step2.dp;

public class MaxProfitITest {
    /**
     * 买卖股票，不限制买卖的次数。可以使用贪心去做，这里我们考虑使用动态规划去做，
     *
     * 通过总结出一套模版，去秒杀所有的股票类型的题
     *
     * i：第几天，K：允许交易的最大次数，s：当前的持有状态（1：当前持有股票，0：当前未持有股票）
     * dp[i][k][s]：我们用一个三维数组就可以装下这几种状态的全部组合。
     * 注意：这里的交易指的是一次买入和一次卖出的过程
     *
     * 状态转移方程：
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     *               max( 今天选择 rest,        今天选择 sell       )
     * 解释：今天我没有持有股票，有两种可能，我从这两种可能中求最大利润：
     *
     * 1、我昨天就没有持有，且截至昨天最大交易次数限制为 k；然后我今天选择 rest，所以我今天还是没有持有，最大交易次数限制依然为 k。
     *
     * 2、我昨天持有股票，且截至昨天最大交易次数限制为 k；但是今天我 sell 了，所以我今天没有持有股票了，最大交易次数限制依然为 k。
     *
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
     *               max( 今天选择 rest,         今天选择 buy         )
     * 解释：今天我持有着股票，最大交易次数限制为 k，那么对于昨天来说，有两种可能，我从这两种可能中求最大利润：
     *
     * 1、我昨天就持有着股票，且截至昨天最大交易次数限制为 k；然后今天选择 rest，所以我今天还持有着股票，最大交易次数限制依然为 k。
     *
     * 2、我昨天本没有持有，且截至昨天最大交易次数限制为 k - 1；但今天我选择 buy，所以今天我就持有股票了，最大交易次数限制为 k。
     *
     * 这里着重提醒一下，时刻牢记「状态」的定义，状态 k 的定义并不是「已进行的交易次数」，而是「最大交易次数的上限限制」。
     * 如果确定今天进行一次交易，且要保证截至今天最大交易次数上限为 k，那么昨天的最大交易次数上限必须是 k - 1。
     * 注意 k 的限制，在选择 buy 的时候相当于开启了一次交易，那么对于昨天来说，交易次数的上限 k 应该减小 1。
     *
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/submissions/
     */

    /**
     * 限制一次买卖，这里我们使用统一的框架去解决，当然在2022-leetcode-step1-dp-MaxProfit中的写法空间复杂度更低。
     *
     * dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
     * dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
     *             = max(dp[i-1][1][1], -prices[i])
     * 解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。
     *
     * 现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
     * 可以进行进一步化简去掉所有 k：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], -prices[i])
     *
     */
    public int maxProfit_k_1(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        //初始化
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        //填剩下的位置
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);//我今天没有持有股票，可能1：前一天我也没有持有股票，今天无操作；可能2：前一天我持有股票，今天我选择卖出。
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);//我今天持有股票，可能1：前一天我也持有股票，今天无操作；可能2：前一天我没有持有股票，今天我选择买入。
        }
        return dp[n - 1][0]; //在第n-1天，我将手里的股票卖掉的情况下能获得的最大利润
    }

    /**
     * 不限制买卖次数，也就是k为无穷
     * 如果 k 为正无穷，那么就可以认为 k 和 k - 1 是一样的。可以这样改写框架：
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
     *             = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
     *
     * 我们发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
     */
    public int maxProfit_k_inf(int[] prices){
        int n = prices.length;
        int[][] dp = new int[n][2];
        //初始化
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        //填剩下的位置
        for (int i = 1; i < n; i++) {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); //我今天没有持有股票，可能1：前一天我也没有持有股票，今天无操作；可能2：前一天我持有股票，今天我选择卖出。
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); //我今天持有股票，可能1：前一天我也持有股票，今天无操作；可能2：前一天我没有持有股票，今天我选择买入。
        }
        return dp[n - 1][0]; //在第n-1天，我将手里的股票卖掉的情况下能获得的最大利润
    }
}
